/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package somtsp;

/**
 *
 * @author Rex Boris
 */
//====================================================================
// Tsp.java
// Travelling Salesman Problem: Algorithm Module
//====================================================================
import java.lang.*;

public class Tsp extends Thread {

    int N, M, CITY_NUM;
    double x[][];
    double w[][];
    double d[];    // distance between x and node
    int Nc;
    int d_Nc;
    double d_eta;
    double change;
    int end_check;
    int t;
    boolean thread_control;
    Counter ct, r_dist;
    Tsp_Display td;

    //------------------------------------------------------------------
    Tsp(Tsp_Param tp, int dne, int deta,
            Counter c, Counter r, Tsp_Display t) {
        CITY_NUM = tp.CITY_NUM;
        d_Nc = dne;
        d_eta = deta;
        ct = c;
        r_dist = r;
        td = t;
        N = 2;
        M = CITY_NUM * 3;
        Nc = CITY_NUM / 2;
        init();
        x_set(tp);
    }

    //------------------------------------------------------------------
    public void x_set(Tsp_Param tp) {
        x = new double[CITY_NUM][N];
        for (int j = 0; j < CITY_NUM; j++) {
            for (int i = 0; i < N; i++) {
                x[j][i] = tp.x[j][i];
            }
        }
    }

    //------------------------------------------------------------------
    public void init() {
        w = new double[M][N];
        d = new double[M];
        for (int j = 0; j < M; j++) {
            for (int i = 0; i < N; i++) {
                w[j][i] = Math.random() / 10.0;
            }
        }
        t = 0;
    }

    //------------------------------------------------------------------
    //step 2, 3
    public void distance(int k) {
        for (int j = 0; j < M; j++) {
            d[j] = 0.0;
            for (int i = 0; i < N; i++) {
                d[j] += (x[k][i] - w[j][i]) * (x[k][i] - w[j][i]);
            }
        }
    }

    //------------------------------------------------------------------
    // step4
    public int selectNode() {
        int j, k;

        for (j = 0, k = 0; k < M; k++) {
            if (d[j] > d[k]) {
                j = k;
            }
        }
        return j;
    }

    //------------------------------------------------------------------
    // step5:
    public void renew_w(int j, int k) {
        int i, l, m;
        double eta;

        if (d_eta > 0) {
            eta = 1.0 / (double) (t + 2);
        } else {
            eta = 1.0 / Math.log((double) (t + 3));
        }
        for (m = j - Nc; m <= j + Nc; m++) {
            l = m;
            if (l < 0) {
                l += M;
            } else if (l >= M) {
                l -= M;
            }
            for (i = 0; i < N; i++) {
                w[l][i] = w[l][i] + eta * (x[k][i] - w[l][i]);
            }
        }
    }

    //------------------------------------------------------------------
    public double Ring_distance() {
        double dist = 0.0;
        for (int i = 0; i < M - 1; i++) {
            dist += Math.sqrt((w[i][0] - w[i + 1][0]) * (w[i][0] - w[i + 1][0])
                    + (w[i][1] - w[i + 1][1]) * (w[i][1] - w[i + 1][1]));
        }
        dist += Math.sqrt((w[M - 1][0] - w[0][0]) * (w[M - 1][0] - w[0][0])
                + (w[M - 1][1] - w[0][1]) * (w[M - 1][1] - w[0][1]));
        return dist;
    }

    //----------------------------------------------------------------
    public void run() {
        int i = 0, j = 0, k = 0, l = 0, m = 0;
        double change = 0.001;
        double pre_w[] = new double[N];
        while (thread_control) {
            if (i >= d_Nc && Nc > 0) {
                Nc--;
                i = 0;
            }
            if (d_eta > 0 && m >= d_eta) {
                t++;
                m = 0;
            }
            if (d_eta < 0) {
                t++;
            }
            if (k >= CITY_NUM) {
                k -= CITY_NUM;
            }
            distance(k);	// Step 2 & 3
            j = selectNode();	// Step 4
            pre_w[0] = w[j][0];
            pre_w[1] = w[j][1];
            renew_w(j, k);	// Step 5
            if (Math.abs(pre_w[0] - w[j][0]) < change
                    && Math.abs(pre_w[1] - w[j][1]) < change) {
                end_check++;	// check nodes' change
            } else {
                end_check = 0;
            }
            if (end_check >= CITY_NUM) {
                thread_control = false; // loop stop
                r_dist.setValue(Ring_distance());
            }
            i++;
            k++;
            l++;
            m++;
            synchronized (td) {
                td.paintTsp(this);
            }
            ct.count_up();
            try {
                sleep(30);
            } catch (Exception e) {
            }
        }
    }
}
